package com.lw.leetcode.back.b;

/**
 * back
 * 526. 优美的排列
 *
 * @Author liw
 * @Date 2021/6/30 21:07
 * @Version 1.0
 */
public class CountArrangement {

    public static void main(String[] args) {
        CountArrangement test = new CountArrangement();
        // {0,1,2,3,8,10,36,41,132,250,700,750,4010,4237,10680,24679};
        for (int i = 1; i <= 15; i++) {
            System.out.println(test.countArrangement(i));
        }

    }

    /*
    采用回溯算法：
    1:创建一个n长的数组 arr，其中每个元素的值 为  i + 1, 例如： [1,2,3,4,5],用来记录每个数字是否使用。
    2:若使用了，则把其值设置为0，使用完毕，再回复原值。
    3：是否能够使用，则是判断其能否和对应的索引值取模是否为0。
    4:用把数组中的数字都用完了，则说明是符合条件的一个解，则count + 1。
     */

    private int count;
    private int[] arr;
    private int n;

    public int countArrangement(int n) {
        this.n = n;
        this.arr = new int[n];
        this.count = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }
        find(0);
        return count;
    }

    private void find(int index) {
        if (index == n) {
            count++;
            return;
        }
        for (int i = 0; i < n; i++) {
            int value = arr[i];
            if (value == 0) {
                continue;
            }
            if (value % (index + 1) != 0 && (index + 1) % value != 0) {
                continue;
            }
            arr[i] = 0;
            find(index + 1);
            arr[i] = value;
        }
    }

}
